/*
实验6-4 D 度完全树
分数 30
作者 陈越
单位 浙江大学

给定一棵 D 度完全树的前序遍历序列，请输出该树的层序遍历序列。并且，对任意给定的结点，请输出从该结点到根结点的路径。
输入格式：

输入第 1 行给出 2 个正整数 n（≤50）和 d（2≤d≤5），分别是树中结点个数和树的度。随后一行给出 n 个不超过 100 的整数键值，
为树的前序遍历序列。
最后给出整数 k（≤n）以及 k 个结点的位置，这里结点位置是指该结点在层序遍历中的位序，从 0 开始。一行中的数字用空格分隔。

输出格式：

首先在一行中输出这个 D 度完全树的层序遍历序列。随后对于每个输入的结点位置，在一行中输出从该结点到根结点的路径。注意同行数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：

9 3
91 71 2 34 10 15 55 18 7
3
5 7 3

输出样例：

91 71 15 7 2 34 10 55 18
34 71 91
55 15 91
7 91
*/

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cmath>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* parent;
    vector<TreeNode*> children;
    TreeNode(int v) : val(v), parent(nullptr) {}
};

// 计算树的高度
int get_height(int n, int d) {
    int m = d;
    int h = 1;
    while (true) {
        int sum = (m-1)/(d-1);
        if (sum >= n) {
            break;
        }
        m *= d;
        h++;
    }
    return h;
}

TreeNode* build_tree(const vector<int>& preorder, const int d, const int height, const int depth, int& index, int &leftLeaf) {
    if (index >= preorder.size() || depth > height) { // 空节点
        index++;
        return nullptr;
    }

    if (depth == height && leftLeaf == 0) return nullptr;

    // 创建当前节点
    TreeNode* node = new TreeNode(preorder[index]);
    index++; // 移动到下一个节点
    if (depth == height) {
        leftLeaf--;
        return node;
    }

    // 计算当前节点的子节点数量
    for (int i = 0; i < d; i++) {
        TreeNode* child = build_tree(preorder, d, height, depth + 1, index, leftLeaf);
        if (child) { // 如果子节点不为空
            node->children.push_back(child);
            child->parent = node;
        }
    }

    return node;
}

void level_order(TreeNode* root, vector<TreeNode*>& levelOrder) {
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        levelOrder.push_back(node);
        for (TreeNode* child : node->children) {
            q.push(child);
        }
    }
}

void path_to_root(TreeNode* node) {
    cout << node->val;
    while (node->parent) {
        cout << " " << node->parent->val;
        node = node->parent;
    }
    cout << endl;
}

int main() {
    int n, d;
    cin >> n >> d;
    vector<int> preorder(n);
    for (int i = 0; i < n; ++i) {
        cin >> preorder[i];
    }
    int idx = 0;
    int height = get_height(n, d);
    int leftLeaf = n - (pow(d, height - 1) - 1) / (d - 1);
    TreeNode* root = build_tree(preorder, d, height, 1, idx, leftLeaf);

    vector<TreeNode*> levelOrder;
    level_order(root, levelOrder);

    bool first = true;
    for (int i = 0; i < levelOrder.size(); ++i) {
        if (!first) cout << " ";
        first = false;
        cout << levelOrder[i]->val;
    }
    cout << endl;
    
    int k;
    cin >> k;
    for (int i = 0; i < k; ++i) {
        int pos;
        cin >> pos;
        path_to_root(levelOrder[pos]);
    }
    return 0;
}